package LeetCode;

import java.util.HashMap;
import java.util.Map;

public class LC_525_ContiguousArray {

    public static void main(String[] args) {

    }

    class Solution_1 {
        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int maxlen = 0, count = 0;
            for (int i = 0; i < nums.length; i++) {
                count = count + (nums[i] == 1 ? 1 : -1);
                if (map.containsKey(count)) {
                    maxlen = Math.max(maxlen, i - map.get(count));
                } else {
                    map.put(count, i);
                }
            }
            return maxlen;
        }
    }

    public class Solution_2 {
        public int countArrangement(int N) {
            int[] num = new int[N];
            return findWay(num, 1);
        }

        int findWay(int[] num, int index) {
            if (index == num.length + 1) return 1;
            int total = 0;
            for (int i = 0; i < num.length; i++) {
                if (num[i] != 1) {
                    if ((i + 1) % index == 0 || index % (i + 1) == 0) {
                        int[] newNum = num.clone();
                        newNum[i] = 1;
                        total += findWay(newNum, index + 1);
                    }
                }
            }
            return total;
        }

    }
}